home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / zoo21src.zoo / lzd.asm < prev    next >
Assembly Source File  |  1991-07-24  |  10KB  |  451 lines
  1. title    Lempel-Ziv Decompressor
  2. ; $Source$
  3. ; $Id$
  4.  
  5. ;Derived from Tom Pfau's public domain assembly code.
  6. ;The contents of this file are hereby released to the public domain.
  7. ;                                   -- Rahul Dhesi 1988/08/24
  8.  
  9. UNBUF_IO    equ    1        ;use unbuffered I/O
  10.  
  11. public    _lzd,memflag,docrc
  12.  
  13.     include    asmconst.ai
  14.     include macros.ai
  15.  
  16. ;Hash table entry
  17. hash_rec    struc
  18. next    dw    ?            ; prefix code
  19. char    db    ?            ; suffix char
  20. hash_rec    ends
  21.  
  22. extrn    _addbfcrc:near            ;External C function for CRC
  23.  
  24. ifdef    UNBUF_IO
  25. extrn    _read:near
  26. extrn    _blockwrite:near
  27. else
  28. extrn    _zooread:near
  29. extrn    _zoowrite:near
  30. endif
  31.  
  32. ;Declare segments
  33. _text    segment byte public 'code'
  34. _text    ends
  35.  
  36. dgroup    group    _data
  37.     assume ds:dgroup,es:dgroup
  38. _data    segment word public 'data'
  39. extrn    _out_buf_adr:word        ;address of C output buffer
  40. extrn    _in_buf_adr:word        ;address of C input buffer
  41.  
  42. memflag        db    0        ;Memory allocated?  flag
  43. save_bp        dw    ?
  44. save_sp        dw    ?
  45.  
  46. input_handle    dw    ?
  47. output_handle    dw    ?
  48. hash_seg    dw    ?
  49. cur_code    dw    ?
  50. old_code    dw    ?
  51. in_code        dw    ?
  52. free_code    dw    first_free
  53.  
  54. ;Note:  for re-entrancy, following 3 must be re-initialized each time
  55. stack_count    dw    0
  56. nbits        dw    9
  57. max_code    dw    512
  58.  
  59. fin_char    db    ?
  60. k        db    ?
  61. masks        dw    1ffh,3ffh,7ffh,0fffh,1fffh
  62.  
  63. ;Note:  for re-entrancy, following 2 must be re-initialized each time
  64. bit_offset    dw    0
  65. output_offset    dw    0
  66. _data    ends
  67.  
  68. memory    segment para public 'memory'
  69. hash    label    hash_rec
  70. memory    ends
  71.  
  72. call_index macro
  73.     mov    bp,bx            ;bx = bx * 3 (3 byte entries)
  74.     shl    bx,1            ;bp = bx
  75.     add    bx,bp            ;bx = bx * 2 + bp
  76.     endm
  77.  
  78. call_write_char macro
  79.     local    wc$1
  80.     mov    di,output_offset    ;Get offset in buffer
  81.     cmp    di,outbufsiz        ;Full?
  82.     jb    wc$1            ;no
  83.     call    write_char_partial
  84.     sub    di,di            ;so we add zero in next statement
  85. wc$1:    add    di,[_out_buf_adr]    ;di <- buffer address + di
  86.     stosb                ;Store char
  87.     inc    output_offset        ;Increment number of chars in buffer
  88.     endm
  89.  
  90. add_code macro
  91.     mov    bx,free_code        ;Get new code
  92.     ;call    index            ;convert to address
  93.     call_index
  94.     push    es            ;point to hash table
  95.     mov    es,hash_seg
  96.     mov    al,k            ;get suffix char
  97.     mov    es:[bx].char,al        ;save it
  98.     mov    ax,old_code        ;get prefix code
  99.     mov    es:[bx].next,ax        ;save it
  100.     pop    es
  101.     inc    free_code        ;set next code
  102.     endm
  103.  
  104. ;Start coding
  105. _text    segment
  106.     assume    cs:_text,ds:dgroup,es:dgroup,ss:nothing
  107.  
  108. write_char_partial proc    near
  109.     push    cx
  110.     mov    cx,di            ;byte count
  111.     call    write_block
  112.     pop    cx
  113.     mov    output_offset,0        ;Restore buffer pointer
  114.     ret
  115. write_char_partial endp
  116.  
  117. _lzd    proc    near
  118.  
  119.     push    bp            ;Standard C entry code
  120.     mov    bp,sp
  121.     push    di
  122.     push    si
  123.     
  124.     push    ds            ;Save ds to be sure
  125.     mov    [save_bp],bp        ;And bp too!
  126.     mov    bx,ds
  127.     mov    es,bx
  128.  
  129. ;Get two parameters, both integers, that are input file handle and
  130. ;output file handle
  131.     mov    ax,[bp+4]
  132.     mov    [input_handle],ax
  133.     mov    ax,[bp+6]
  134.     mov    [output_handle],ax
  135.  
  136.     call    decompress        ;Compress file & get status in AX
  137.  
  138.     mov    bp,[save_bp]        ;Restore bp
  139.     pop    ds
  140.     pop    si            ;Standard C return code
  141.     pop    di
  142.     mov    sp,bp
  143.     pop    bp
  144.     ret
  145. _lzd    endp
  146.  
  147. ;Note:  Procedure decompress returns AX=0 for successful decompression and
  148. ;    AX=1 for I/O error and AX=2 for malloc failure.  
  149. decompress    proc    near
  150.     mov    [save_sp],sp        ;Save SP in case of error return
  151.  
  152. ;Initialize variables -- required for serial re-entrancy
  153.     mov    [nbits],9
  154.     mov    [max_code],512
  155.     mov    [free_code],first_free
  156.     mov    [stack_count],0
  157.     mov    [bit_offset],0
  158.     mov    [output_offset],0
  159.  
  160.     test    memflag,0ffH        ;Memory allocated?
  161.     jnz    gotmem            ;If allocated, continue
  162.     malloc    <((maxmax * 3) / 16 + 20)>    ;allocate it
  163.     jnc    here1
  164.     jmp    MALLOC_err
  165. here1:
  166.     mov    hash_seg,ax        ;Save segment address of mem block
  167.     mov    memflag,0ffh        ;Set flag to remind us later
  168. gotmem:
  169.  
  170.     mov    ax,inbufsiz
  171.     push    ax            ;byte count
  172.     push    _in_buf_adr        ;buffer address
  173.     push    input_handle        ;zoofile
  174. ifdef    UNBUF_IO
  175.     call    _read
  176. else
  177.     call    _zooread
  178. endif
  179.     add    sp,6
  180.  
  181.     cmp    ax,-1
  182.     jz    IO_err            ;I/O error
  183. here2:
  184.  
  185. l1:    call    read_code        ;Get a code
  186.     cmp    ax,eof            ;End of file?
  187.     jne    l2            ;no
  188.     cmp    output_offset,0        ;Data in output buffer?
  189.     je    OK_ret            ;no
  190.     mov    cx,[output_offset]    ;byte count
  191.     call    write_block        ;write block of cx bytes
  192. OK_ret:    
  193.     xor    ax,ax            ;Normal return -- decompressed
  194.     ret                ;done
  195. IO_err:
  196.     mov    ax,2            ;I/O error return 
  197.     mov    sp,[save_sp]        ;Restore stack pointer
  198.     ret    
  199.  
  200. MALLOC_err:
  201.     mov    ax,1            ;Malloc error return
  202.     mov    sp,[save_sp]        ;Restore stack pointer
  203.     ret
  204.  
  205. l2:    cmp    ax,clear        ;Clear code?
  206.     jne    l7            ;no
  207.     call    init_tab        ;Initialize table
  208.     call    read_code        ;Read next code
  209.     mov    cur_code,ax        ;Initialize variables
  210.     mov    old_code,ax
  211.     mov    k,al
  212.     mov    fin_char,al
  213.     mov    al,k
  214.     ;call    write_char        ;Write character
  215.     call_write_char
  216.     jmp    l1            ;Get next code
  217. l7:    mov    cur_code,ax        ;Save new code
  218.     mov    in_code,ax
  219.     mov    es,hash_seg        ;Point to hash table
  220.     cmp    ax,free_code        ;Code in table? (k<w>k<w>k)
  221.     jb    l11            ;yes
  222.     mov    ax,old_code        ;get previous code
  223.     mov    cur_code,ax        ;make current
  224.     mov    al,fin_char        ;get old last char
  225.     push    ax            ;push it
  226.     inc    stack_count
  227.  
  228. ;old code -- two memory references
  229. ;l11:    
  230. ;    cmp    cur_code,255        ;Code or character?
  231. ;    jbe    l15            ;Char
  232. ;    mov    bx,cur_code        ;Convert code to address
  233. ;new code -- 0 or 1 memory references
  234.     mov    ax,cur_code
  235. l11:
  236.     ;All paths in must have ax containing cur_code
  237.     cmp    ax,255
  238.     jbe    l15
  239.     mov    bx,ax
  240. ;end code
  241.     ;call    index
  242.     call_index
  243.     mov    al,es:2[bx]        ;Get suffix char
  244.     push    ax            ;push it
  245.     inc    stack_count
  246.     mov    ax,es:[bx]        ;Get prefix code
  247.     mov    cur_code,ax        ;Save it
  248.     jmp    l11            ;Translate again
  249. l15:    
  250. ;old code
  251. ;    push    ds            ;Restore seg reg
  252. ;    pop    es
  253. ;new code
  254.     mov    ax,ds            ;faster than push/pop
  255.     mov    es,ax
  256. ;end code
  257.     mov    ax,cur_code        ;Get code
  258.     mov    fin_char,al        ;Save as final, k
  259.     mov    k,al
  260.     push    ax            ;Push it
  261.  
  262. ;old code
  263. ;    inc    stack_count
  264. ;    mov    cx,stack_count        ;Pop stack
  265. ;new code -- slightly faster because INC of memory is slow
  266.     mov    cx,stack_count
  267.     inc    cx
  268.     mov    stack_count,cx
  269. ;end code
  270.     jcxz    l18            ;If anything there
  271. l17:    pop    ax
  272.     ;call    write_char
  273.     call_write_char
  274.     loop    l17
  275.  
  276. ;old code
  277. ;l18:    
  278. ;    mov    stack_count,cx        ;Clear count on stack
  279. ;new code -- because stack_count is already zero on earlier "jcxz l18"
  280.     mov    stack_count,cx
  281. l18:
  282. ;end code
  283.  
  284.     ;call    add_code        ;Add new code to table
  285.     add_code
  286.     mov    ax,in_code        ;Save input code
  287.     mov    old_code,ax
  288.     mov    bx,free_code        ;Hit table limit?
  289.     cmp    bx,max_code
  290.     jb    l23            ;Less means no
  291.     cmp    nbits,maxbits        ;Still within maxbits?
  292.     je    l23            ;no (next code should be clear)
  293.     inc    nbits            ;Increase code size
  294.     shl    max_code,1        ;Double max code
  295. l23:    jmp    l1            ;Get next code
  296. decompress    endp    
  297.  
  298. read_code    proc    near
  299.  
  300. ;old code
  301. ;    mov    ax,bit_offset        ;Get bit offset
  302. ;    add    ax,nbits        ;Adjust by code size
  303. ;    xchg    bit_offset,ax        ;Swap
  304. ;    mov    dx,ax            ;dx <- ax
  305. ;new code
  306.     mov    ax,bit_offset
  307.     mov    dx,ax            ;dx <- bit_offset
  308.     add    ax,nbits
  309.     mov    bit_offset,ax
  310.     mov    ax,dx
  311. ;end code
  312.  
  313.     shr    ax,1
  314.     shr    ax,1
  315.     shr    ax,1            ;ax <- ax div 8
  316.     and    dx,07            ;dx <- ax mod 8
  317.     cmp    ax,inbufsiz-3        ;Approaching end of buffer?
  318.     jb    rd0            ;no
  319.     push    dx            ;Save offset in byte
  320.     add    dx,nbits        ;Calculate new bit offset
  321.     mov    bit_offset,dx
  322.     mov    cx,inbufsiz
  323.     mov    bp,ax            ;save byte offset
  324.     sub    cx,ax            ;Calculate bytes left
  325.     add    ax,_in_buf_adr
  326.     mov    si,ax
  327.     mov    di,_in_buf_adr
  328. rep    movsb                ;Move last chars down
  329.  
  330.     push    bp            ;byte count
  331.     push    di            ;buffer address
  332.     push    input_handle        ;zoofile
  333. ifdef    UNBUF_IO
  334.     call _read
  335. else
  336.     call    _zooread
  337. endif
  338.     add    sp,6
  339.  
  340.     cmp    ax,-1
  341.     jnz    here4
  342.     jmp    IO_err            ;I/O error
  343.  
  344. here4:
  345.     xor    ax,ax            ;Clear ax
  346.     pop    dx            ;Restore offset in byte
  347. rd0:    
  348.     add    ax,_in_buf_adr
  349.     mov    si,ax
  350.     lodsw                ;Get word
  351.     mov    bx,ax            ;Save in AX
  352.     lodsb                ;Next byte
  353.     mov    cx,dx            ;Offset in byte
  354.     jcxz    rd2            ;If zero, skip shifts
  355. rd1:    shr    al,1            ;Put code in low (code size) bits of BX
  356.     rcr    bx,1
  357.     loop    rd1
  358. rd2:    mov    ax,bx            ;put code in ax
  359.     mov    bx,nbits        ;mask off unwanted bits
  360.     sub    bx,9
  361.     shl    bx,1
  362.     and    ax,masks[bx]
  363.     ret
  364. read_code    endp
  365.  
  366. init_tab    proc    near
  367.     mov    nbits,9            ;Initialize variables
  368.     mov    max_code,512
  369.     mov    free_code,first_free
  370.     ret
  371. init_tab    endp
  372.  
  373. comment #
  374. index        proc    near
  375.     mov    bp,bx            ;bx = bx * 3 (3 byte entries